//给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"]
//,["1","0","0","1","0"]]
//输出：6
//解释：最大矩形如上图所示。
// 
//
// 示例 2： 
//
// 
//输入：matrix = []
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：matrix = [["0"]]
//输出：0
// 
//
// 示例 4： 
//
// 
//输入：matrix = [["1"]]
//输出：1
// 
//
// 示例 5： 
//
// 
//输入：matrix = [["0","0"]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// rows == matrix.length 
// cols == matrix[0].length 
// 1 <= row, cols <= 200 
// matrix[i][j] 为 '0' 或 '1' 
// 
// Related Topics 栈 数组 动态规划 矩阵 单调栈 👍 1308 👎 0

package leetcode.editor.cn;

import java.util.Stack;

class MaximalRectangle {
    public static void main(String[] args) {
        Solution solution = new MaximalRectangle().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maximalRectangle(char[][] matrix) {
            if (matrix.length == 0) return 0;
            int[] height = new int[matrix[0].length];
            int maxSize = 0;

            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == '1') {
                        height[j] += 1;
                    }else {
                        height[j] = 0;
                    }
                }
                maxSize = Math.max(largestRectangleArea(height), maxSize);
            }

            return maxSize;
        }

        public int largestRectangleArea(int[] heights) {
            if (heights.length == 0) return 0;
            Stack<Integer> stack = new Stack<>();
            int size = 0;
            int[] newHeights = new int[heights.length + 2];
            for (int i = 0; i < heights.length; i++) {
                newHeights[i + 1] = heights[i];
            }
            heights = newHeights;
            stack.push(0);

            for (int i = 1; i < heights.length; i++) {
                if (heights[stack.peek()] <= heights[i]) {
                    stack.push(i);
                } else if (heights[stack.peek()] > heights[i]) {
                    while (heights[stack.peek()] > heights[i]) {
                        int height = heights[stack.peek()];
                        stack.pop();
                        int left = stack.peek();
                        int width = i - left - 1;
                        size = Math.max(height * width, size);
                    }
                    stack.push(i);
                }
            }

            return size;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
